package huisu;

import java.util.*;

public class Solution {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean used[];
    int digit = 0;
    public List<List<Integer>> subsets(int[] nums) {
        used = new boolean[nums.length];
        //ans.add(new ArrayList<>());
        dfs(nums);
        return ans;
    }
    public void dfs(int[] nums){
        for(int i = 0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            list.add(nums[i]);
            used[i] = true;
            digit++;
           dfs(nums);
            list.removeLast();
            used[i] = false;
            digit--;
        }
        if(digit<=nums.length){
            ans.add(new ArrayList<>(list));
        }
    }
}
class Tel{
    /*
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
     */
    Map<Character,String> m = new HashMap<>();
    List<String> res = new ArrayList<>();
    List<Character> list = new ArrayList<>();
    int  digit = 0;
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()){
            return res;
        }
        char[] ch = digits.toCharArray();
        m.put('2',"abc");
        m.put('3',"def");
        m.put('4',"ghi");
        m.put('5',"jkl");
        m.put('6',"mno");
        m.put('7',"pqrs");
        m.put('8',"tuv");
        m.put('9',"wxyz");
        back(ch,0);
        return res;
    }
    public void back(char[] ch,int index){
        for(int i = index;i<ch.length;i++){
            for(int j = 0;j<m.get(ch[i]).length();j++){
                list.add(m.get(ch[i]).charAt(j));
                digit++;
                back(ch,i+1);
                list.removeLast();
                digit--;
            }
        }
        if(digit == ch.length) {
            String str = "";
            for(char c : list){
                str+=c;
            }
            res.add(str);
        }
    }

}
class KuoHao{
    /*
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
     */
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder  temp = new StringBuilder();
        back(n,0,0,temp);
        return res;
    }
    public void back(int n,int left,int right,StringBuilder temp){
        if(left==n&&right==n){
            String str = temp.toString();
            res.add(str);
        }
           if(left<n){
               temp.append('(');
               back(n,left+1,right,temp);
               temp.deleteCharAt(temp.length()-1);
           }
           if(right<n&&right+1<=left){
               temp.append(')');
               back(n,left,right+1,temp);
               temp.deleteCharAt(temp.length()-1);
           }
    }

}
class Sum_HuiSu{
    /*
   给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
    */
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
    public void dfs(int[] candidates,int target,int sum,int index){
      for(int i = index;i<candidates.length;i++){
           if(sum>=target){
               break;
           }
           list.add(candidates[i]);
           sum+=candidates[i];
           dfs(candidates,target,sum,index);
           list.removeLast();
           sum-=candidates[i];
           index++;
      }
      if(sum==target){
          res.add(new ArrayList<>(list));
      }
    }
}

class ZuHe_Three {
    /*
    找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
     */
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        int [] nums = {1,2,3,4,5,6,7,8,9};
        int num = k;
        dfs(nums,k,n,0,0,num);
        return res;
    }
    public void dfs(int[] nums,int k,int n,int index,int sum,int num){
        for(int i = index;i<nums.length;i++){
            if(k==0){
                break;
            }
            if(sum>=n){
                break;
            }
            sum+=nums[i];
            list.add(nums[i]);
            k--;
            dfs(nums,k,n,i+1,sum,num);
            sum-=nums[i];
            list.removeLast();
            k++;
        }
        if(sum == n&&list.size() == num){
            res.add(new ArrayList<>(list));
        }
    }
}
class Alpha{
    /*
    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
     */
    char[][] board;
    char [] cs;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        cs = word.toCharArray();
        for(int i = 0; i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(dfs(0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(int l,int i,int j){
        if(l == cs.length){
            return true;
        }
        if(i<0||j<0||i>=board.length||j>=board[0].length){
            return false;
        }
        if(board[i][j]==cs[l]){
            char temp = board[i][j];
            board[i][j] = '.';
            l++;
            boolean ret = dfs(l,i+1,j)||dfs(l,i-1,j)||dfs(l,i,j+1)||dfs(l,i,j-1);
            board[i][j] = temp;
            return ret;
        }
        return false;
        /*
         if(l==cs.length){
            return true;
        }
        if(i<0||j<0||i>=board.length||j>board[0].length){
            return false;
        }
        if(board[i][j] == cs[l]){
            char temp = board[i][j];
            board[i][j] = '.';
            l++;
            boolean ret = dfs(l,i+1,j)||dfs(l,i-1,j)||dfs(l,i,j+1)||dfs(l,i,j-1);
            board[i][j] = temp;
            return ret;
        }
        return false;
         */
    }
}
class N_Queen{
    /*
    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
     */
    List<String> list = new ArrayList<>();
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
            if(n<1){
                return res;
            }
            int [] record = new int[n];
            process(0,record,n);
            return res;
    }
    public void process(int i,int [] record,int n){
        if(list.size() == n){
            res.add(new ArrayList<>(list));
        }
        if(i==n){
            return;
        }
        char [] str = new char [n];
        for(int k = 0;k<str.length;k++){
            str[k]='.';
        }
        for(int j = 0;j<n;j++){
            if(isValid(record,i,j)){
                str[j] = 'Q';
                record[i] = j;
                list.add(String.valueOf(str));
                process(i+1,record,n);
                list.removeLast();
                for(int k = 0;k<str.length;k++){
                    str[k]='.';
                }
            }
        }
    }
    public boolean isValid(int [] record,int i,int j){
        for(int k = 0; k < i;k++){
            if(j == record[k]||Math.abs(i-k)==Math.abs(j-record[k])){
                return false;
            }
        }
        return true;
    }
}

class N_Queen2 {
    /*
       n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
   给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
       */
    //不能超过32皇后,int只有32位
    public int totalNQueens(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;//32位数中的后面n位为1，前面都为0
        return process(limit, 0, 0, 0);
    }

    /*
    colLim 列限制，即皇后不能同一列 1表示当前这个位置不能放皇后，0表示这个位置可以放
    leftDiaLim 左斜线限制,皇后不能同一斜线
    rightDiaLim右斜线限制
    */
    public int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {//所有列都放好了皇后，说明找到一种放皇后且不让皇后之间相互攻击的策略
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;
        pos = limit & (~(colLim | rightDiaLim | leftDiaLim));//排除被限制的位置，可选位置全为1
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);//找到pos最右边的1
            pos = pos - mostRightOne;
            res += process(limit, colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);//将右斜线右移一位，左斜线左移一位得到下一行的限制条件
        }
        return res;
    }

}
class  HuiWen{
    /*
    一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
     */
    List<String> list = new ArrayList<>();
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        process(s,0);
        return res;
    }
    public void process(String s,int index){
        if(index>=s.length()){
            res.add(new ArrayList<>(list));
        }
        for(int i = index;i<s.length();i++){
            String str = s.substring(index,i+1);
            if(isValid(s,index,i)){
                list.add(str);
            }else{
                continue;
            }
            process(s,i+1);
            list.removeLast();
        }
    }
    public boolean isValid(String s,int l,int r){
        while(l<=r){
            if(s.charAt(l)!=s.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return  true;
    }
}
class Test{
    public static void main(String[] args) {
        HuiWen huiWen = new HuiWen();
        List<List<String>> aab = huiWen.partition("aab");
    }
}
